# dfs回溯
class Solution(object):
    def hasPath(self, matrix, string):
        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        def dfs(i, j, u):
            if matrix[i][j] != string[u]:
                return False
            if u == len(string) - 1:
                return True
            t = matrix[i][j]
            matrix[i][j] = '!'
            for k in range(4):
                x, y = i + dx[k], j + dy[k]
                if x >= 0 and y >= 0 and x < len(matrix) and y < len(matrix[0]):
                    if dfs(x, y, u + 1):
                        return True
            matrix[i][j] = t
            return False

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == string[0]:
                    if dfs(i, j, 0):
                        return True
        return False